package puzzle.projecteuler.p200;

import java.util.Arrays;
import java.util.Comparator;

import astudy.util.AdvMath;
import astudy.util.Pair;
import astudy.util.AdvMath.Factors;

public class Problem124C {

	/**
	 * @param args
	 */
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {

		Pair<Integer, Integer>[] ps = new Pair[100000];
		for (int i = 0; i < 100000; i ++) {
			int n = i+1;
			if (n == 1) {
				ps[i] = new Pair(n, 1);
			} else {
				Factors fs = AdvMath.factor(n);
				int m = 1;
				for (Long k: fs.keySet()) {
					m *= k;
				}
				ps[i] = new Pair(n, m);
			}
		}
		//sort them
		Arrays.sort(ps, new Comparator<Pair<Integer, Integer>>(){

			public int compare(Pair<Integer, Integer> o1,
					Pair<Integer, Integer> o2) {
				if (o1.getSecond().compareTo(o2.getSecond()) == 0) {
					return o1.getFirst().compareTo(o2.getFirst());
				} else {
					return o1.getSecond().compareTo(o2.getSecond());
				}
			}}
		);
		System.out.println(ps[10000-1].getFirst());
	}
}
